package org.demo.algorithm;
/**
 * 用回溯法计算组合数
 * @author  
 * @date    2010-9-14
 * @file    org.demo.algorithm.Combination2.java
 */
public class Combination2 {
	// 源数据
	private static String[] source;
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {
		source = new String[]{"A","B","C","D","E"};
		int m = source.length;
		int k = 3;
		int[] data = new int[k];
		// 计算 C(m, k)
		backtrace(0, k, m, data);
	}			
	/**
	 * 回溯法求解
	 * @param level 当前层次 0<=level<=deep
	 * @param deep  最大深度 0< deep <=max
	 * @param max   总结点数 deep <= max
	 * @param data  辅助数组：用来存储一组解,data.length == deep
	 */
	public static void backtrace(int level,int deep,int max,int[] data){
	    if (level >= deep){
	    	// 到达解空间树的最底层时，输出当前解
	        output(data);
	        return;
	    }
	    for(int i=start(level,data);i<=end(level,deep,max);i++){
	        // 取下一个值
	        data[level] = i;
	        // 进行深度优先搜索
	        backtrace(level+1,deep,max,data);
	        // 回溯
	        data[level] = 0;
	    }
	}
	/**
	 * 起始值
	 * @param level 当前层次
	 * @param data  辅助数组：用来存储一组解
	 * @return
	 */
	private static int start(int level,int[] data){
	    if(level == 0){
	        return 1;
	    }
	    return data[level-1] + 1;
	}
	/**
	 * 终止值
	 * @param level 当前层次
	 * @param deep  最大深度
	 * @param max   总结点数
	 * @return
	 */
	private static int end(int level,int deep,int max){
	    return max-deep+level +1;
	}
	/**
	 * 输出数据
	 * @param data
	 */
	private static void output(int[] data){
		for (int k=0; k<data.length; k++){
			int idx = data[k]-1;
            System.out.print(source[idx]);
        }
		System.out.println();
	}
}
